#$Id: heapsort.py 6 2008-11-24 15:21:18Z Eric.Nevup $

def shift_down(alist, p_node, size):
    """Make a tree as max heap,
    Assuming that left tree and right tree are already a max heap.

    alist,  data
    p_node, the root node index in the list
    size,   the size of heap, may be not equals to len(alist)
    """
    while (True):
        l_node = p_node * 2
        r_node = l_node + 1
        largest = p_node
        if (l_node < size and alist[l_node] > alist[largest]):
            largest = l_node
        if (r_node < size and alist[r_node] > alist[largest]):
            largest = r_node
        if (largest != p_node):
            alist[largest], alist[p_node] = (alist[p_node], alist[largest])
            p_node = largest
        else:
            break    

def heapify(alist):
    """from the last non-leaf node to root, do shift_down"""
    for i in range((len(alist) - 1) // 2, 0, -1):
        shift_down(alist, i, len(alist))

def heap_sort(alist):
    if (len(alist) <= 2):
        return
    """Build max heap"""
    heapify(alist)
    
    """Sort by swaping root and last node,
       decreasing heap size and shift_down from root."""
    for i in range(len(alist) - 1, 1, -1):
        alist[1], alist[i] = (alist[i], alist[1])
        shift_down(alist, 1, i)
        

seq = [9999,9,8,7,6,5,4,3,2,1,1,2,3,5,4,3,9,6]
heap_sort(seq)
print(seq)

